package cn.edu.xjtu.work.intersect;

import java.util.List;
import java.util.Map;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Hashtable;

/**
 * 350. 两个数组的交集 II
 * 
 * 给定两个数组，编写一个函数来计算它们的交集。
 */
public class Solution {
  public static void main(String[] args) {
    // int[] nums1 = new int[] { 1, 2, 2, 1 };
    // int[] nums2 = new int[] { 2, 2 };
    int[] nums1 = new int[] { 4, 9, 5 };
    int[] nums2 = new int[] { 9, 4, 9, 8, 4 };
    System.out.println(Arrays.toString(intersect2(nums1, nums2)));
  }

  /**
   * 先对数组进行排序,然后从两个数组起点开始遍历,如果两个指针指向元素一样,那么继续处理下一个,否则将指向元素较小的指针向后移动,直到有一个到达终点
   * 
   * @param nums1
   * @param nums2
   * @return
   */
  public static int[] intersect2(int[] nums1, int[] nums2) {
    List<Integer> ret = new ArrayList<>();
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    int point1 = 0;// 指向nums1的指针
    int point2 = 0;// 指向nums2的指针
    while (point1 < nums1.length && point2 < nums2.length) {
      if (nums1[point1] < nums2[point2]) {
        point1++;
      } else if (nums1[point1] > nums2[point2]) {
        point2++;
      } else {
        ret.add(nums1[point1]);
        point1++;
        point2++;
      }
    }
    int[] arr = new int[ret.size()];
    for (int i = 0; i < arr.length; i++) {
      arr[i] = ret.get(i);
    }
    return arr;
  }

  /**
   * 使用hashtable完成,将任意一个数组加入map中,key为数组中的值,value为出现的次数,对另一个数组进行遍 历,同时更新map中的值
   * 
   * @param nums1
   * @param nums2
   * @return
   */
  public static int[] intersect1(int[] nums1, int[] nums2) {
    List<Integer> ret = new ArrayList<>();
    Map<Integer, Integer> array1 = new Hashtable<>();
    for (int i = 0; i < nums1.length; i++) {
      array1.put(nums1[i], array1.getOrDefault(nums1[i], 0) + 1);
    }
    for (int i = 0; i < nums2.length; i++) {
      if (array1.containsKey(nums2[i])) {
        if (array1.get(nums2[i]) == 1) {
          array1.remove(nums2[i]);
        } else {
          array1.put(nums2[i], array1.get(nums2[i]) - 1);
        }
        ret.add(nums2[i]);
      }
    }
    int[] arr = new int[ret.size()];
    for (int i = 0; i < arr.length; i++) {
      arr[i] = ret.get(i);
    }
    return arr;
  }
}
